package B刷题.A栈和队列;

import java.util.Stack;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：用一个栈实现另一个栈的排序
 * @date 2022/12/5 10:39
 */
public class Code06_SortStackByStack {

    /**
     * 思路：逐个弹出，确保前N位有序，直至弹空，然后放回原栈。
     * 充分理解栈的特点：将一个栈的数据逐个弹出放入另一个栈，顺序相反；再逐个弹出放回原栈，顺序相同。
     */
    public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            while (!help.isEmpty()&&help.peek()<pop){
                stack.add(help.pop());
            }
            help.add(pop);
        }
        while (!help.isEmpty()){
            stack.add(help.pop());
        }
    }

}
